The increase in computational speed achieved by modern computer technology has enabled the widespread use of electronic techniques for the communication and storage of documents of many types. For purposes of this application, the term "documents" will refer to two-dimensional representations or renderings of a nature that are conventionally made on a paper medium or on a graphics display by writing, printing, typing, drawing, operation of a computer-aided draw, paint or design program, or other similar conventional techniques, and those renderings that are commonly stored on paper, microfilm, microfiche, or electronically. Examples of such documents include, without limitation thereto, text documents, bank checks and other banking transaction records, vital records, maps, charts, printed works (including combinations of text and graphics), seismic plots, medical records, bank and insurance records, directories, and the like. As is well known to the public, examples of conventional electronic communication and storage of documents includes modern digital facsimile ("fax") equipment, CD-ROM storage and distribution of encyclopedias and other series of books, electronically or magnetically stored representations of transactions such as checks and other banking transactions and statements, and the like.
Electronic communication and storage is made quite difficult for those documents in which a significant portion of the information contained in many documents is in the form of graphic information which cannot readily be coded into computer-readable form on a character-by-character basis. For example, while the letters in a person's signature may readily be electronically communicated by way of an ASCII coded representation on a character-by-character basis, the retrieval of the ASCII coded representation will not provide any information regarding the appearance of the signature as made by the person. To electronically communicate or store documents with graphic information, the conventional technique is to digitize the document into a bit-map representation, with each memory location in the bit map corresponding to an elemental position of the document, and with the contents of the memory locations corresponding to the color at that location. In the case of a "binary" digital document representations, for example, the digital value "0" may be used to represent the color black and the digital value "1" may be used to represent the color white.
Of course, it is highly desirable that the digitizing of documents be performed with as high a resolution as possible, which requires the use of a significant amount of memory for each document page. For example, current high resolution digitization devotes on the order of greater than one million bits to store a binary bit map representation of a single monochromatic (black and white) document page divided into 1024-by-1024 picture elements, or "pixels". On a 300 dpi laser printer, this 1k-by-1k picture will be printed on a paper area of approximately three inches by three inches. Therefore, even finer resolution may be required for larger high quality pictures to be printed, and also for certain types of documents, such as fingerprint files utilized by law enforcement agencies.
These high resolution digitally stored representations of documents obviously not only occupy a great deal of computer memory and hard disk storage space, but also require significant time for their transmission over conventional communication lines. As such, conventional data compression techniques are highly useful in the electronic communication and storage of documents. Conventional data compression techniques are generally referred to as of either "lossless" or "lossy", depending upon whether data is discarded in the compression process. For most digitized documents with graphics information, lossy data compression techniques may be used, so long as the receiver is still able to distinguish the graphic image with acceptable clarity.
A survey of conventional lossy data compression techniques may be found at Simon, "How Lossy Data Compression Shrinks Image Files", PC Magazine (Jul. 1993), pp. 371 et seq. A popular one of these conventional lossy data compression techniques is referred to as the JPEG (Joint Photographic Experts Group) method. A description of this technique may be found in Barnsley and Hurd, Fractal Image Compression (AK Peters, Ltd., 1993), pp. 219-228. The JPEG compression method initially divides the image into blocks of pixels, and a Discrete Cosine Transform (DCT) is performed on each pixel block, producing a representation of the block as coefficients corresponding to frequencies and amplitudes, rather than corresponding directly to color information. These coefficients are then quantized, or rounded off, and a difference algorithm is performed over all quantized blocks in the image, in a selected scan order. This difference algorithm subtracts a DC term corresponding to the mean pixel value of a block, from the DC term of the preceding block. The difference coefficients are then scanned in a different order, such as a zig-zag order, and the non-zero coefficients (i.e., blocks in which a difference from the preceding block occurred) are coded to indicate the number of preceding zero coefficients (i.e., the number of pixel blocks in which no change occurred) and also the value of the non-zero difference. Lossless compression is then often applied to the coded result to further compress the data. Decompression is performed by reversing the compression process, producing the displayable image.
Another conventional method of lossy video image compression, referred to as Recursive Vector Quantization (RVQ), quantizes the pixel blocks directly, without a DCT or other transform, according to a set of selected reference tiles. See Simon, July 1993, op. cit.. The reference tiles are selected according to an iterative technique, based upon the accuracy of the results relative to the original image. As noted in the Simon article, compression according to the. RVQ method is computationally intense and complex, but decompression can be done quite rapidly.
Another type of conventional lossy video image compression techniques is referred to as fractal compression. As is well known in the art, a fractal is a mathematical image object that is self-similar, in that the image can be represented in terms of other pieces of the image. In fractal image compression, the input image is similarly divided into pixel groups, or tiles. Each tile is then approximated by a transformation (contractive, rotational, or both) of one or more other reference regions of the image. The compressed image thus consists of a full representation of the reference region, plus the transformation operators for each of the tiles. Each tile of the image is decompressed by performing a transformation of the reference region using the stored transformation operator for that tile. Detailed descriptions of conventional fractal image compression techniques and systems for performing the same may be found in Barnsley & Hurd, Fractal Image Compression (AK Peters, Ltd., 1993), in U.S. Pat. No. 4,941,193, and in U.S. Pat. No. 5,065,447.
Wavelet-based techniques are also known to be used for the data compression of digitally stored documents. An summary of this technique, as applied to the compression of digitized fingerprint files used in law enforcement, is described in Bradley and Brislawn, "The Wavelet/Scalar Quantization compression Standard for Digital Fingerprint Images", Tec Rep LA-UR-94-827, Proc. IEEE ISCAS-94 (IEEE, 1994). This approach utilizes the well-known Daubechies wavelet, applied to the document data by way of a table look-up technique. The Daubechies wavelet function used .in this case is not bounded, however, and as such boundary effects may be present in the reconstruction; indeed, the approach described in the Bradley and Brislawn paper attempts to reduce boundary effects by reflecting the wavelet filters at the image boundaries. Furthermore, this prior approach is generalized to 8-bit images (i.e., for compression of full grey scale images). Use of this approach for documents, particularly for binary documents, will thus be especially cumbersome considering the size of the array to be considered in the image compression process, and the eventual compression ratio will be somewhat limited.
By way of further background, the technique of byte packing as a lossless compression technique is well known in the field of computer data storage. According to this well-known technique, digital values that may be expressed by fewer bits are packed with other similar values into a single byte. For example, if eight bit words are used to express a stream of data having only two values, e.g., 255.sub.2 and 0.sub.2, byte packing will allow the data stream to be expressed with a single bit per value. Each byte (eight bits) will thus be able to express the same information as eight bytes of raw data.
By way of further background, our copending application Ser. No. 08/181,663, filed Jan. 14, 1994, entitled "Method and Apparatus for Video Image Compression and Decompression Using Boundary-Spline-Wavelets", assigned to Houston Advanced Research Center and incorporated herein by this reference, describes a wavelet analysis-based approach to video compression, particularly in the field of motion pictures. This application Ser. No. 08/181,663 also provides a discussion of the background theory of wavelet analysis, and its application to image compression.
It is an object of the present invention to provide a method and apparatus for compressing digitized representation of documents to a high degree, in such a manner that the resolution and fidelity of the received document upon decompression is maintained.
It is a further object of the present invention to provide such a method and apparatus in which the decompressed document may be magnified to an arbitrary extent.
It is a further object of the present invention to provide such a method and apparatus in which boundary effects are effectively eliminated in the compressed document, thus improving the quality of the compressed document and also enabling zoom-in and zoom-out techniques to be applied to the reconstructed document.
It is a further object of the present invention to provide such a method and apparatus in which the compression may be performed by integer operations, increasing the speed of the compression and enabling relatively low cost computing equipment (or hardware) to perform the compression quickly.
It is a further object of the present invention to provide such a method and apparatus that is suitable for storage and communication of compressed digitized documents.
It is another object of the present invention to provide such a method and apparatus in which the compression technique is selectable.
Other objects and advantages of the present invention will be apparent to those of ordinary skill in the art having reference to the following specification together with its drawings.